/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.cf.code;

import java.util.ArrayList;

import com.android.dx.rop.code.LocalItem;
import com.android.dx.rop.cst.Constant;
import com.android.dx.rop.cst.CstFieldRef;
import com.android.dx.rop.cst.CstInteger;
import com.android.dx.rop.cst.CstInterfaceMethodRef;
import com.android.dx.rop.cst.CstMethodRef;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Prototype;
import com.android.dx.rop.type.Type;
import com.android.dx.util.Hex;

/**
 * Class which knows how to simulate the effects of executing bytecode.
 * <p>
 * <b>Note:</b> This class is not thread-safe. If multiple threads need to use a
 * single instance, they must synchronize access explicitly between themselves.
 * </p>
 */
public class Simulator {

	/**
	 * {@code non-null;} canned error message for local variable table
	 * mismatches
	 */
	private static final String LOCAL_MISMATCH_ERROR = "This is symptomatic of .class transformation tools that ignore "
			+ "local variable information.";

	/** {@code non-null;} machine to use when simulating */
	private final Machine machine;

	/** {@code non-null;} array of bytecode */
	private final BytecodeArray code;

	/** {@code non-null;} local variable information */
	private final LocalVariableList localVariables;

	/** {@code non-null;} visitor instance to use */
	private final SimVisitor visitor;

	/**
	 * Constructs an instance.
	 * 
	 * @param machine
	 *            {@code non-null;} machine to use when simulating
	 * @param method
	 *            {@code non-null;} method data to use
	 */
	public Simulator(Machine machine, ConcreteMethod method) {
		if (machine == null) {
			throw new NullPointerException("machine == null");
		}

		if (method == null) {
			throw new NullPointerException("method == null");
		}

		this.machine = machine;
		this.code = method.getCode();
		this.localVariables = method.getLocalVariables();
		this.visitor = new SimVisitor();
	}

	/**
	 * Simulates the effect of executing the given basic block. This modifies
	 * the passed-in frame to represent the end result.
	 * 
	 * @param bb
	 *            {@code non-null;} the basic block
	 * @param frame
	 *            {@code non-null;} frame to operate on
	 */
	public void simulate(ByteBlock bb, Frame frame) {
		int end = bb.getEnd();

		visitor.setFrame(frame);

		try {
			for (int off = bb.getStart(); off < end; /* off */) {
				int length = code.parseInstruction(off, visitor);
				visitor.setPreviousOffset(off);
				off += length;
			}
		} catch (SimException ex) {
			frame.annotate(ex);
			throw ex;
		}
	}

	/**
	 * Simulates the effect of the instruction at the given offset, by making
	 * appropriate calls on the given frame.
	 * 
	 * @param offset
	 *            {@code >= 0;} offset of the instruction to simulate
	 * @param frame
	 *            {@code non-null;} frame to operate on
	 * @return the length of the instruction, in bytes
	 */
	public int simulate(int offset, Frame frame) {
		visitor.setFrame(frame);
		return code.parseInstruction(offset, visitor);
	}

	/**
	 * Constructs an "illegal top-of-stack" exception, for the stack
	 * manipulation opcodes.
	 */
	private static SimException illegalTos() {
		return new SimException("stack mismatch: illegal "
				+ "top-of-stack for opcode");
	}

	/**
	 * Returns the required array type for an array load or store instruction,
	 * based on a given implied type and an observed actual array type.
	 * <p>
	 * The interesting cases here have to do with object arrays,
	 * <code>byte[]</code>s, <code>boolean[]</code>s, and known-nulls.
	 * </p>
	 * <p>
	 * In the case of arrays of objects, we want to narrow the type to the
	 * actual array present on the stack, as long as what is present is an
	 * object type. Similarly, due to a quirk of the original bytecode
	 * representation, the instructions for dealing with <code>byte[]</code> and
	 * <code>boolean[]</code> are undifferentiated, and we aim here to return
	 * whichever one was actually present on the stack.
	 * </p>
	 * <p>
	 * In the case where there is a known-null on the stack where an array is
	 * expected, we just fall back to the implied type of the instruction. Due
	 * to the quirk described above, this means that source code that uses
	 * <code>boolean[]</code> might get translated surprisingly -- but correctly
	 * -- into an instruction that specifies a <code>byte[]</code>. It will be
	 * correct, because should the code actually execute, it will necessarily
	 * throw a <code>NullPointerException</code>, and it won't matter what
	 * opcode variant is used to achieve that result.
	 * </p>
	 * 
	 * @param impliedType
	 *            {@code non-null;} type implied by the instruction; is
	 *            <i>not</i> an array type
	 * @param foundArrayType
	 *            {@code non-null;} type found on the stack; is either an array
	 *            type or a known-null
	 * @return {@code non-null;} the array type that should be required in this
	 *         context
	 */
	private static Type requiredArrayTypeFor(Type impliedType,
			Type foundArrayType) {
		if (foundArrayType == Type.KNOWN_NULL) {
			return impliedType.getArrayType();
		}

		if ((impliedType == Type.OBJECT) && foundArrayType.isArray()
				&& foundArrayType.getComponentType().isReference()) {
			return foundArrayType;
		}

		if ((impliedType == Type.BYTE)
				&& (foundArrayType == Type.BOOLEAN_ARRAY)) {
			/*
			 * Per above, an instruction with implied byte[] is also allowed to
			 * be used on boolean[].
			 */
			return Type.BOOLEAN_ARRAY;
		}

		return impliedType.getArrayType();
	}

	/**
	 * Bytecode visitor used during simulation.
	 */
	private class SimVisitor implements BytecodeArray.Visitor {

		/**
		 * {@code non-null;} machine instance to use (just to avoid excessive
		 * cross-object field access)
		 */
		private final Machine machine;

		/**
		 * {@code null-ok;} frame to use; set with each call to
		 * {@link Simulator#simulate}
		 */
		private Frame frame;

		/** offset of the previous bytecode */
		private int previousOffset;

		/**
		 * Constructs an instance.
		 */
		public SimVisitor() {
			this.machine = Simulator.this.machine;
			this.frame = null;
		}

		/**
		 * Sets the frame to act on.
		 * 
		 * @param frame
		 *            {@code non-null;} the frame
		 */
		public void setFrame(Frame frame) {
			if (frame == null) {
				throw new NullPointerException("frame == null");
			}

			this.frame = frame;
		}

		/** {@inheritDoc} */
		public void visitInvalid(int opcode, int offset, int length) {
			throw new SimException("invalid opcode " + Hex.u1(opcode));
		}

		/** {@inheritDoc} */
		public void visitNoArgs(int opcode, int offset, int length, Type type) {
			switch (opcode) {
			case ByteOps.NOP: {
				machine.clearArgs();
				break;
			}
			case ByteOps.INEG: {
				machine.popArgs(frame, type);
				break;
			}
			case ByteOps.I2L:
			case ByteOps.I2F:
			case ByteOps.I2D:
			case ByteOps.I2B:
			case ByteOps.I2C:
			case ByteOps.I2S: {
				machine.popArgs(frame, Type.INT);
				break;
			}
			case ByteOps.L2I:
			case ByteOps.L2F:
			case ByteOps.L2D: {
				machine.popArgs(frame, Type.LONG);
				break;
			}
			case ByteOps.F2I:
			case ByteOps.F2L:
			case ByteOps.F2D: {
				machine.popArgs(frame, Type.FLOAT);
				break;
			}
			case ByteOps.D2I:
			case ByteOps.D2L:
			case ByteOps.D2F: {
				machine.popArgs(frame, Type.DOUBLE);
				break;
			}
			case ByteOps.RETURN: {
				machine.clearArgs();
				checkReturnType(Type.VOID);
				break;
			}
			case ByteOps.IRETURN: {
				Type checkType = type;
				if (type == Type.OBJECT) {
					/*
					 * For an object return, use the best-known type of the
					 * popped value.
					 */
					checkType = frame.getStack().peekType(0);
				}
				machine.popArgs(frame, type);
				checkReturnType(checkType);
				break;
			}
			case ByteOps.POP: {
				Type peekType = frame.getStack().peekType(0);
				if (peekType.isCategory2()) {
					throw illegalTos();
				}
				machine.popArgs(frame, 1);
				break;
			}
			case ByteOps.ARRAYLENGTH: {
				Type arrayType = frame.getStack().peekType(0);
				if (!arrayType.isArrayOrKnownNull()) {
					throw new SimException("type mismatch: expected "
							+ "array type but encountered "
							+ arrayType.toHuman());
				}
				machine.popArgs(frame, Type.OBJECT);
				break;
			}
			case ByteOps.ATHROW:
			case ByteOps.MONITORENTER:
			case ByteOps.MONITOREXIT: {
				machine.popArgs(frame, Type.OBJECT);
				break;
			}
			case ByteOps.IALOAD: {
				/*
				 * See comment on requiredArrayTypeFor() for explanation about
				 * what's going on here.
				 */
				Type foundArrayType = frame.getStack().peekType(1);
				Type requiredArrayType = requiredArrayTypeFor(type,
						foundArrayType);

				// Make type agree with the discovered requiredArrayType.
				type = requiredArrayType.getComponentType();

				machine.popArgs(frame, requiredArrayType, Type.INT);
				break;
			}
			case ByteOps.IADD:
			case ByteOps.ISUB:
			case ByteOps.IMUL:
			case ByteOps.IDIV:
			case ByteOps.IREM:
			case ByteOps.IAND:
			case ByteOps.IOR:
			case ByteOps.IXOR: {
				machine.popArgs(frame, type, type);
				break;
			}
			case ByteOps.ISHL:
			case ByteOps.ISHR:
			case ByteOps.IUSHR: {
				machine.popArgs(frame, type, Type.INT);
				break;
			}
			case ByteOps.LCMP: {
				machine.popArgs(frame, Type.LONG, Type.LONG);
				break;
			}
			case ByteOps.FCMPL:
			case ByteOps.FCMPG: {
				machine.popArgs(frame, Type.FLOAT, Type.FLOAT);
				break;
			}
			case ByteOps.DCMPL:
			case ByteOps.DCMPG: {
				machine.popArgs(frame, Type.DOUBLE, Type.DOUBLE);
				break;
			}
			case ByteOps.IASTORE: {
				/*
				 * See comment on requiredArrayTypeFor() for explanation about
				 * what's going on here. In addition to that, the category 1 vs.
				 * 2 thing below is to deal with the fact that, if the element
				 * type is category 2, we have to skip over one extra stack slot
				 * to find the array.
				 */
				ExecutionStack stack = frame.getStack();
				int peekDepth = type.isCategory1() ? 2 : 3;
				Type foundArrayType = stack.peekType(peekDepth);
				boolean foundArrayLocal = stack.peekLocal(peekDepth);

				Type requiredArrayType = requiredArrayTypeFor(type,
						foundArrayType);

				/*
				 * Make type agree with the discovered requiredArrayType if it
				 * has local info.
				 */
				if (foundArrayLocal) {
					type = requiredArrayType.getComponentType();
				}

				machine.popArgs(frame, requiredArrayType, Type.INT, type);
				break;
			}
			case ByteOps.POP2:
			case ByteOps.DUP2: {
				ExecutionStack stack = frame.getStack();
				int pattern;

				if (stack.peekType(0).isCategory2()) {
					// "form 2" in vmspec-2
					machine.popArgs(frame, 1);
					pattern = 0x11;
				} else if (stack.peekType(1).isCategory1()) {
					// "form 1"
					machine.popArgs(frame, 2);
					pattern = 0x2121;
				} else {
					throw illegalTos();
				}

				if (opcode == ByteOps.DUP2) {
					machine.auxIntArg(pattern);
				}
				break;
			}
			case ByteOps.DUP: {
				Type peekType = frame.getStack().peekType(0);

				if (peekType.isCategory2()) {
					throw illegalTos();
				}

				machine.popArgs(frame, 1);
				machine.auxIntArg(0x11);
				break;
			}
			case ByteOps.DUP_X1: {
				ExecutionStack stack = frame.getStack();

				if (!(stack.peekType(0).isCategory1() && stack.peekType(1)
						.isCategory1())) {
					throw illegalTos();
				}

				machine.popArgs(frame, 2);
				machine.auxIntArg(0x212);
				break;
			}
			case ByteOps.DUP_X2: {
				ExecutionStack stack = frame.getStack();

				if (stack.peekType(0).isCategory2()) {
					throw illegalTos();
				}

				if (stack.peekType(1).isCategory2()) {
					// "form 2" in vmspec-2
					machine.popArgs(frame, 2);
					machine.auxIntArg(0x212);
				} else if (stack.peekType(2).isCategory1()) {
					// "form 1"
					machine.popArgs(frame, 3);
					machine.auxIntArg(0x3213);
				} else {
					throw illegalTos();
				}
				break;
			}
			case ByteOps.DUP2_X1: {
				ExecutionStack stack = frame.getStack();

				if (stack.peekType(0).isCategory2()) {
					// "form 2" in vmspec-2
					if (stack.peekType(2).isCategory2()) {
						throw illegalTos();
					}
					machine.popArgs(frame, 2);
					machine.auxIntArg(0x212);
				} else {
					// "form 1"
					if (stack.peekType(1).isCategory2()
							|| stack.peekType(2).isCategory2()) {
						throw illegalTos();
					}
					machine.popArgs(frame, 3);
					machine.auxIntArg(0x32132);
				}
				break;
			}
			case ByteOps.DUP2_X2: {
				ExecutionStack stack = frame.getStack();

				if (stack.peekType(0).isCategory2()) {
					if (stack.peekType(2).isCategory2()) {
						// "form 4" in vmspec-2
						machine.popArgs(frame, 2);
						machine.auxIntArg(0x212);
					} else if (stack.peekType(3).isCategory1()) {
						// "form 2"
						machine.popArgs(frame, 3);
						machine.auxIntArg(0x3213);
					} else {
						throw illegalTos();
					}
				} else if (stack.peekType(1).isCategory1()) {
					if (stack.peekType(2).isCategory2()) {
						// "form 3"
						machine.popArgs(frame, 3);
						machine.auxIntArg(0x32132);
					} else if (stack.peekType(3).isCategory1()) {
						// "form 1"
						machine.popArgs(frame, 4);
						machine.auxIntArg(0x432143);
					} else {
						throw illegalTos();
					}
				} else {
					throw illegalTos();
				}
				break;
			}
			case ByteOps.SWAP: {
				ExecutionStack stack = frame.getStack();

				if (!(stack.peekType(0).isCategory1() && stack.peekType(1)
						.isCategory1())) {
					throw illegalTos();
				}

				machine.popArgs(frame, 2);
				machine.auxIntArg(0x12);
				break;
			}
			default: {
				visitInvalid(opcode, offset, length);
				return;
			}
			}

			machine.auxType(type);
			machine.run(frame, offset, opcode);
		}

		/**
		 * Checks whether the prototype is compatible with returning the given
		 * type, and throws if not.
		 * 
		 * @param encountered
		 *            {@code non-null;} the encountered return type
		 */
		private void checkReturnType(Type encountered) {
			Type returnType = machine.getPrototype().getReturnType();

			/*
			 * Check to see if the prototype's return type is possibly
			 * assignable from the type we encountered. This takes care of all
			 * the salient cases (types are the same, they're compatible
			 * primitive types, etc.).
			 */
			if (!Merger.isPossiblyAssignableFrom(returnType, encountered)) {
				throw new SimException("return type mismatch: prototype "
						+ "indicates " + returnType.toHuman()
						+ ", but encountered type " + encountered.toHuman());
			}
		}

		/** {@inheritDoc} */
		public void visitLocal(int opcode, int offset, int length, int idx,
				Type type, int value) {
			/*
			 * Note that the "type" parameter is always the simplest type based
			 * on the original opcode, e.g., "int" for "iload" (per se) and
			 * "Object" for "aload". So, when possible, we replace the type with
			 * the one indicated in the local variable table, though we still
			 * need to check to make sure it's valid for the opcode.
			 * 
			 * The reason we use (offset + length) for the localOffset for a
			 * store is because it is only after the store that the local type
			 * becomes valid. On the other hand, the type associated with a load
			 * is valid at the start of the instruction.
			 */
			int localOffset = (opcode == ByteOps.ISTORE) ? (offset + length)
					: offset;
			LocalVariableList.Item local = localVariables.pcAndIndexToLocal(
					localOffset, idx);
			Type localType;

			if (local != null) {
				localType = local.getType();
				if (localType.getBasicFrameType() != type.getBasicFrameType()) {
					BaseMachine.throwLocalMismatch(type, localType);
					return;
				}
			} else {
				localType = type;
			}

			switch (opcode) {
			case ByteOps.ILOAD:
			case ByteOps.RET: {
				machine.localArg(frame, idx);
				machine.localInfo(local != null);
				machine.auxType(type);
				break;
			}
			case ByteOps.ISTORE: {
				LocalItem item = (local == null) ? null : local.getLocalItem();
				machine.popArgs(frame, type);
				machine.auxType(type);
				machine.localTarget(idx, localType, item);
				break;
			}
			case ByteOps.IINC: {
				LocalItem item = (local == null) ? null : local.getLocalItem();
				machine.localArg(frame, idx);
				machine.localTarget(idx, localType, item);
				machine.auxType(type);
				machine.auxIntArg(value);
				machine.auxCstArg(CstInteger.make(value));
				break;
			}
			default: {
				visitInvalid(opcode, offset, length);
				return;
			}
			}

			machine.run(frame, offset, opcode);
		}

		/** {@inheritDoc} */
		public void visitConstant(int opcode, int offset, int length,
				Constant cst, int value) {
			switch (opcode) {
			case ByteOps.ANEWARRAY: {
				machine.popArgs(frame, Type.INT);
				break;
			}
			case ByteOps.PUTSTATIC: {
				Type fieldType = ((CstFieldRef) cst).getType();
				machine.popArgs(frame, fieldType);
				break;
			}
			case ByteOps.GETFIELD:
			case ByteOps.CHECKCAST:
			case ByteOps.INSTANCEOF: {
				machine.popArgs(frame, Type.OBJECT);
				break;
			}
			case ByteOps.PUTFIELD: {
				Type fieldType = ((CstFieldRef) cst).getType();
				machine.popArgs(frame, Type.OBJECT, fieldType);
				break;
			}
			case ByteOps.INVOKEINTERFACE: {
				/*
				 * Convert the interface method ref into a normal method ref.
				 */
				cst = ((CstInterfaceMethodRef) cst).toMethodRef();
				// and fall through...
			}
			case ByteOps.INVOKEVIRTUAL:
			case ByteOps.INVOKESPECIAL: {
				/*
				 * Get the instance prototype, and use it to direct the machine.
				 */
				Prototype prototype = ((CstMethodRef) cst).getPrototype(false);
				machine.popArgs(frame, prototype);
				break;
			}
			case ByteOps.INVOKESTATIC: {
				/*
				 * Get the static prototype, and use it to direct the machine.
				 */
				Prototype prototype = ((CstMethodRef) cst).getPrototype(true);
				machine.popArgs(frame, prototype);
				break;
			}
			case ByteOps.MULTIANEWARRAY: {
				/*
				 * The "value" here is the count of dimensions to create. Make a
				 * prototype of that many "int" types, and tell the machine to
				 * pop them. This isn't the most efficient way in the world to
				 * do this, but then again, multianewarray is pretty darn rare
				 * and so not worth much effort optimizing for.
				 */
				Prototype prototype = Prototype.internInts(Type.VOID, value);
				machine.popArgs(frame, prototype);
				break;
			}
			default: {
				machine.clearArgs();
				break;
			}
			}

			machine.auxIntArg(value);
			machine.auxCstArg(cst);
			machine.run(frame, offset, opcode);
		}

		/** {@inheritDoc} */
		public void visitBranch(int opcode, int offset, int length, int target) {
			switch (opcode) {
			case ByteOps.IFEQ:
			case ByteOps.IFNE:
			case ByteOps.IFLT:
			case ByteOps.IFGE:
			case ByteOps.IFGT:
			case ByteOps.IFLE: {
				machine.popArgs(frame, Type.INT);
				break;
			}
			case ByteOps.IFNULL:
			case ByteOps.IFNONNULL: {
				machine.popArgs(frame, Type.OBJECT);
				break;
			}
			case ByteOps.IF_ICMPEQ:
			case ByteOps.IF_ICMPNE:
			case ByteOps.IF_ICMPLT:
			case ByteOps.IF_ICMPGE:
			case ByteOps.IF_ICMPGT:
			case ByteOps.IF_ICMPLE: {
				machine.popArgs(frame, Type.INT, Type.INT);
				break;
			}
			case ByteOps.IF_ACMPEQ:
			case ByteOps.IF_ACMPNE: {
				machine.popArgs(frame, Type.OBJECT, Type.OBJECT);
				break;
			}
			case ByteOps.GOTO:
			case ByteOps.JSR:
			case ByteOps.GOTO_W:
			case ByteOps.JSR_W: {
				machine.clearArgs();
				break;
			}
			default: {
				visitInvalid(opcode, offset, length);
				return;
			}
			}

			machine.auxTargetArg(target);
			machine.run(frame, offset, opcode);
		}

		/** {@inheritDoc} */
		public void visitSwitch(int opcode, int offset, int length,
				SwitchList cases, int padding) {
			machine.popArgs(frame, Type.INT);
			machine.auxIntArg(padding);
			machine.auxSwitchArg(cases);
			machine.run(frame, offset, opcode);
		}

		/** {@inheritDoc} */
		public void visitNewarray(int offset, int length, CstType type,
				ArrayList<Constant> initValues) {
			machine.popArgs(frame, Type.INT);
			machine.auxInitValues(initValues);
			machine.auxCstArg(type);
			machine.run(frame, offset, ByteOps.NEWARRAY);
		}

		/** {@inheritDoc} */
		public void setPreviousOffset(int offset) {
			previousOffset = offset;
		}

		/** {@inheritDoc} */
		public int getPreviousOffset() {
			return previousOffset;
		}
	}
}
